package VNF_DelayTest_large_modified02;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.net2plan.interfaces.networkDesign.Demand;
import com.net2plan.interfaces.networkDesign.Link;
import com.net2plan.interfaces.networkDesign.NetPlan;
import com.net2plan.interfaces.networkDesign.NetworkLayer;
import com.net2plan.interfaces.networkDesign.Node;
import com.net2plan.libraries.GraphUtils;

public class MyUtil {
	
	public static int numberofallslot = 300 ;
	public static int numberOfKShortestPath = 3;
	public static int numberOfKLinkmapping = 3;
	public static double BPSKmaxlength = 4000.0;
	public static double QPSKmaxlength = 2000.0;
	public static double QAM_8maxlength = 1000.0;
	public static double QAM_16maxlength = 500.0;

	public static String vnfType;
	
	/**
	 * 移除这个网络中的所有分层
	 * @param netplan 要操作的网络拓扑
	 * @return 默认层
	 */
	public static NetPlan removeLayers(NetPlan netplan){
		List<Long> names = new ArrayList<Long>();
		int numberofnetworklayers = netplan.getNumberOfLayers();
		for (int i=1;i<numberofnetworklayers;i++){
			Long name = netplan.getNetworkLayer(i).getId();
			names.add(name);
		}
		for (Long name : names){
			netplan.removeNetworkLayer(netplan.getNetworkLayerFromId(name));
			netplan = netplan.copy();
		}
		return netplan;
	}
	
	public static NetPlan substrateNetplanAttribute(NetPlan netplan){
		Tool_Util tool = new Tool_Util();
		List<Link> links = new ArrayList<Link>();
		links = netplan.getLinks();
		String capacityofslots = tool.setAttributeOfSituationOfSlots(numberofallslot);
		for (Link link : links){
			link.setAttribute("linkstatus", capacityofslots);
			link.setCapacity(numberofallslot);
		}
		return netplan;
	}
	
	public static NetPlan removeAllLayerDemand(NetPlan netplan){
		for (NetworkLayer networklayer : netplan.getNetworkLayers()){
			netplan.removeAllDemands(networklayer);
		} 
		return netplan;
	}
	
	/**
	 * 对请求集合进行铺设，新的重载方法
	 * @param subNetPlan 物理网络
	 * @param requestList 请求集合
	 */
	public static void nodeMapping(NetPlan subNetPlan,List<NetPlan>requestList) {
		
		//物理网络中的节点数
		int numberOfSubNodes = subNetPlan.getNumberOfNodes();
		//物理网络中的所有节点集合
		List<Node> subNodeList = subNetPlan.getNodes();

		//存放已经铺设完成的请求
		List<NetPlan> deployedRequests = new ArrayList<>();

		//对每个请求进行处理
		for(int requestIndex = 0;requestIndex<requestList.size();requestIndex++) {

			System.out.println(requestIndex);
			NetPlan request = requestList.get(requestIndex);
			
			//存放请求中的节点和物理节点的映射关系
			Map<Node,Node> nodePair = new HashMap<Node,Node>();
			
			//请求中的全部link
			List<Link> requestLinkList = request.getLinks();
			
			//请求中的所有节点数量，包括源节点和目的节点
			int numberOfRequestNodes = request.getNumberOfNodes();
			System.out.println("vnf数量"+(numberOfRequestNodes-2));
			//请求中的VNF节点集合
			List<Node> vnfNodeList = new ArrayList<>();
			for(int i=1;i<numberOfRequestNodes-1;i++) {
				vnfNodeList.add(request.getNode(i));
			}
			//请求中已经铺设完毕的节点，释放资源时使用
			List<Node> tempDeployed = new ArrayList<>();
			//先分配好源节点和目的节点的位置
			Node sourceNode = request.getNode(0);
			Node destinationNode = request.getNode(numberOfRequestNodes-1);
			int sourceNodeIndex,destinationNodeIndex;
			sourceNodeIndex = (int)(Math.random()*numberOfSubNodes);
			System.out.println("源节点"+sourceNodeIndex);
			while(true) {
				destinationNodeIndex = (int)(Math.random()*numberOfSubNodes);
				if(destinationNodeIndex!=sourceNodeIndex) {
					break;
				}
			}
			System.out.println("目的节点"+destinationNodeIndex);
			nodePair.put(sourceNode, subNetPlan.getNode(sourceNodeIndex));
			nodePair.put(destinationNode, subNetPlan.getNode(destinationNodeIndex));
			sourceNode.setAttribute("MappedNode", String.valueOf(sourceNodeIndex));
			destinationNode.setAttribute("MappedNode", String.valueOf(destinationNodeIndex));
			
			//获取源目的节点之间的多条最短路径
			Map<Link,Double> linkCostMap = new HashMap<Link,Double>();
			for(Link link:subNetPlan.getLinks()) {
				linkCostMap.put(link, link.getLengthInKm());
			}
			List<List<Link>> kShortestPathList = GraphUtils.getKLooplessShortestPaths(subNetPlan.getNodes(), subNetPlan.getLinks(), subNetPlan.getNode(sourceNodeIndex), subNetPlan.getNode(destinationNodeIndex), linkCostMap, numberOfKShortestPath, Double.MAX_VALUE, Integer.MAX_VALUE , Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);
			
			boolean nodeMappingSign = false;
			
			LabelB:
			for(int k = 0;k<numberOfKShortestPath;k++) {
				List<Link> candidatePath = kShortestPathList.get(k);
				//存放当前链路上的所有节点
				List<Node> pathNodes = new ArrayList<>();
				pathNodes.add(candidatePath.get(0).getOriginNode());
				for(Link link:candidatePath) {
					pathNodes.add(link.getDestinationNode());
				}
				//存放当前路径上的全部数据中心节点
				List<Node> DCOnPath = new ArrayList<>();
				for(Node node:pathNodes) {
					if("1".equals(node.getAttribute("DataCenter"))) {
						DCOnPath.add(node);
					}
				}
				if(DCOnPath.isEmpty()) {
					continue LabelB;
				}
				//开始处理
				//候选的数据中心集合
				List<Node> candidateDCList = new ArrayList<>();
				int startDCIndex = 0;
				int selectedDCNumber = 0;
				LabelA:
				for(Node vnfNode:vnfNodeList) {
					for(int i=startDCIndex;i<DCOnPath.size();i++) {
						candidateDCList.add(DCOnPath.get(i));
					}
					//节点所需的VNF种类
					vnfType = vnfNode.getAttribute("VNF");
					//将数据中心根据vnf复用的次数升序排列，但是要最后考虑0的情况
					Collections.sort(candidateDCList, (a,b)-> {
						return Integer.valueOf(a.getAttribute(vnfType)).compareTo(Integer.valueOf(b.getAttribute(vnfType)));
					});
					for(int i=0;i<candidateDCList.size();i++) {
						Node tempNode = candidateDCList.get(0);
						if("0".equals(tempNode.getAttribute(vnfType))) {
							//将当前的节点移动到集合的末尾
							MyUtil.moveToEnd(0, candidateDCList);
						}
					}
					
					//对排完序的数据中心节点进行遍历，如果符合条件，就直接考虑下一个vnf节点，如果都不行，那么考虑下一条路径上的数据中心
					LabelC:
					for(int i=0;i<candidateDCList.size();i++) {
						//先选中一个数据中心
						Node selectedDC = candidateDCList.get(i);
						StringBuilder str = new StringBuilder();
						str.append(selectedDC.getAttribute("VNF"));
						int before = Integer.valueOf(selectedDC.getAttribute(vnfType)).intValue();
						if(before==0) {
							str.append(vnfType);
						}
						before++;
						selectedDC.setAttribute("VNF", str.toString());
						selectedDC.setAttribute(vnfType, String.valueOf(before));
						//判断是否对已经铺设好的请求产生了不好的影响
						boolean DCOK = verifyDC(subNetPlan,deployedRequests)&&verifyRequest(subNetPlan,request);
						if(DCOK) {
							tempDeployed.add(vnfNode);
							vnfNode.setAttribute("MappedNode", String.valueOf(subNetPlan.getNodes().indexOf(selectedDC)));
							nodePair.put(vnfNode, selectedDC);
							startDCIndex = DCOnPath.indexOf(selectedDC);
							selectedDCNumber++;
							if(selectedDCNumber==numberOfRequestNodes-2) {
								nodeMappingSign = true;
								break LabelB;
							}
							continue LabelA;
						} else {
							//如果当前节点的铺设对以前的请求产生了不好的影响，那么就要考虑下一个数据中心了
							//先释放之前占用的资源，然后遍历下一个数据中心，如果没有数据中心可以遍历了，那么说明这个请求阻塞
							int current = Integer.valueOf(selectedDC.getAttribute(vnfType)).intValue();
							current--;
							if(current==0) {
								str.deleteCharAt(str.length()-1);
							}
							selectedDC.setAttribute("VNF", str.toString());
							selectedDC.setAttribute(vnfType,String.valueOf(current));
							if(i==candidateDCList.size()-1) {
								//这条路径不可行，先释放掉前面的vnf节点占用的资源，再考虑下一条路径
								//先释放前面的节点占用的资源
								for(Node deployedNode:tempDeployed) {
									if(deployedNode!=null) {
										String vnf = deployedNode.getAttribute("VNF");
										int dcIndex = Integer.valueOf(deployedNode.getAttribute("MappedNode")).intValue();
										Node dc = subNetPlan.getNode(dcIndex);
										StringBuilder stringBuilder = new StringBuilder();
										String temp = dc.getAttribute("VNF");
										stringBuilder.append(temp);
										int num = Integer.valueOf(dc.getAttribute(vnf)).intValue();
										num--;
										if(num==0) {
											stringBuilder.deleteCharAt(stringBuilder.length()-1);
										}
										dc.setAttribute("VNF", stringBuilder.toString());
										dc.setAttribute(vnf, String.valueOf(num));
										nodePair.remove(deployedNode);
									}
								}
								tempDeployed.clear();
								if(k==numberOfKShortestPath-1) {
									//这种情况说明最后一条路径也不行，那么将前面的节点资源释放后，就直接break出大循环，节点映射失败
									nodeMappingSign = false;
									break LabelB;
								} else {
									//还有路径可选，继续下一次循环
									continue LabelB;
								}
							} else {
								//释放完资源后既可以考虑下一个备选数据中心了
								continue LabelC;
							}
						}
					}	
				}
			}
			if(nodePair.size()!=numberOfRequestNodes) {
				nodeMappingSign = false;
			}
			if(!nodeMappingSign) {
				//节点映射失败
				request.setAttribute("block", "1");
				int blockedRequests = Integer.valueOf(subNetPlan.getAttribute("BlockedRequest")).intValue();
				blockedRequests++;
				subNetPlan.setAttribute("BlockedRequest", String.valueOf(blockedRequests));
				System.out.println("节点映射失败");
			} else {
				//节点映射成功
				System.out.println("节点映射成功");
				deployedRequests.add(request);
				for(Link link:requestLinkList) {
					int origin = subNodeList.indexOf(nodePair.get(link.getOriginNode()));
					int destination = subNodeList.indexOf(nodePair.get(link.getDestinationNode()));
					//System.out.println("origin node "+origin+" des node "+destination+" "+link.getCapacity());
					if(origin!=destination) {
						subNetPlan.addDemand(nodePair.get(link.getOriginNode()), nodePair.get(link.getDestinationNode()), link.getCapacity(), null, subNetPlan.getNetworkLayerDefault());
					}
				}
//				for(Node node:request.getNodes()) {
//					System.out.println("DeployedNode:"+node.getAttribute("MappedNode"));
//				}
				//进行节点映射
				LinkMappingReturn linkMappingReturn = new LinkMappingReturn();
				linkMappingReturn = linkMapping(subNetPlan,request);
				
			}
			
		}
		
	}

	//验证当前的铺设方案是否可用
	private static boolean verifyRequest(NetPlan subNetPlan,NetPlan request) {
		double delayTime = calDelayTime(subNetPlan, request);
		double thresTime = Double.valueOf(request.getAttribute("ThreadTime"));
		if(delayTime>thresTime) {
			return false;
		}
		return true;
	}

	/**
	 * 验证是否影响到了已经铺设在网络中的请求
	 * 前面被阻塞掉的请求就不计算了
	 * @param subNetPlan 物理网络
	 * @param requestList 已经铺设完毕的请求集合
	 * @return false 影响到了，true当前铺设方案可行
	 */
	public static boolean verifyDC(NetPlan subNetPlan,List<NetPlan>requestList) {
		boolean res = true;
		
		for(NetPlan formerRequest:requestList) {
			if("0".equals(formerRequest.getAttribute("block"))) {
				//请求没有被阻塞，计算它的延时
				double delayTime = calDelayTime(subNetPlan, formerRequest);
				double thresTime = Double.valueOf(formerRequest.getAttribute("ThreadTime"));
				if(delayTime>thresTime) {
					res = false;
					break;
				}
			}
		}
		return res;
	}
	
	/**
	 * 计算请求的延时
	 * @param subNetPlan 物理网络
	 * @param request 请求
	 * @return 延时
	 */
	public static double calDelayTime(NetPlan subNetPlan,NetPlan request) {
		double delayTime = 0.0;
		List<Node> subNodes = subNetPlan.getNodes();
		for(Node node:request.getNodes()) {
			String vnfType = node.getAttribute("VNF");
			if(!"0".equals(vnfType)) {
				int subIndex = Integer.valueOf(node.getAttribute("MappedNode")).intValue();
				Node subNode = subNodes.get(subIndex);
				int numberOfThisVNF = Integer.valueOf(subNode.getAttribute(vnfType)).intValue();
				int vnf = Integer.valueOf(vnfType).intValue();
				delayTime+=(vnf+1)*5*numberOfThisVNF;
			}
		}
		double pathLength = 0.0;
		for(Link link:request.getLinks(request.getNetworkLayerDefault())) {
			pathLength+=Double.valueOf(link.getAttribute("pathlength")).doubleValue();
		}
		delayTime+=pathLength/200.0;
		return delayTime;
	}
	
	
	/**
	 * 节点映射过程
	 * @param subNetPlan 物理网络
	 * @param request 请求
	 */
	public static NodeMappingReturn nodeMapping(NetPlan subNetPlan,NetPlan request) {
		NodeMappingReturn nodeMappingReturn = new NodeMappingReturn();
		boolean sign = true;
		int sourceNodeIndex,destinationNodeIndex;
		//存放节点之间的对应关系
		Map<Node,Node> nodePair = new HashMap<Node, Node>();
		//存放请求中所需的VNF序列
		List<String> VNFSeq = new ArrayList<String>();
		//选择节点的依据
		Map<Node,Integer> VNFOnDC = new HashMap<Node,Integer>();
		//请求的所有节点数量
		int numberOfRequestNodes = request.getNumberOfNodes();
		//物理网络中的节点数量
		int numberOfSubNodes = subNetPlan.getNumberOfNodes();
		//物理网络中的所有节点
		List<Node> subNodeList = subNetPlan.getNodes();
		//请求中的link集合
		List<Link> requestLinkList = request.getLinks();
		for(int i=1;i<numberOfRequestNodes-1;i++) {
			VNFSeq.add(request.getNode(i).getAttribute("VNF"));
		}
		System.out.print("所需VNF ");
		for(String s : VNFSeq) {
			System.out.print(s+" ");
		}
		System.out.println();
		//先分配好源节点和目的节点的位置
		Node sourceNode = request.getNode(0);
		Node destinationNode = request.getNode(numberOfRequestNodes-1);
		sourceNodeIndex = (int)(Math.random()*numberOfSubNodes);
		System.out.println("源节点"+sourceNodeIndex);
		while(true) {
			destinationNodeIndex = (int)(Math.random()*numberOfSubNodes);
			if(destinationNodeIndex!=sourceNodeIndex) {
				break;
			}
		}
		System.out.println("目的节点"+destinationNodeIndex);
		nodePair.put(sourceNode, subNetPlan.getNode(sourceNodeIndex));
		nodePair.put(destinationNode, subNetPlan.getNode(destinationNodeIndex));
		sourceNode.setAttribute("MappedNode", String.valueOf(sourceNodeIndex));
		destinationNode.setAttribute("MappedNode", String.valueOf(destinationNodeIndex));
		
		//获取源目的节点之间的多条最短路径
		Map<Link,Double> linkCostMap = new HashMap<Link,Double>();
		for(Link link:subNetPlan.getLinks()) {
			linkCostMap.put(link, link.getLengthInKm());
		}
		List<List<Link>> kShortestPathList = GraphUtils.getKLooplessShortestPaths(subNetPlan.getNodes(), subNetPlan.getLinks(), subNetPlan.getNode(sourceNodeIndex), subNetPlan.getNode(destinationNodeIndex), linkCostMap, numberOfKShortestPath, Double.MAX_VALUE, Integer.MAX_VALUE , Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);
		//对所有最短路径上的所有数据中心节点进行遍历
		for(int i=0;i<numberOfKShortestPath;i++) {
			List<Link> shortestPath = kShortestPathList.get(i);
			List<Node> DCNodeOnPath = new ArrayList<Node>();
			Node originNode = shortestPath.get(0).getOriginNode();
			if("1".equals(originNode.getAttribute("DataCenter"))) {
				DCNodeOnPath.add(originNode);
			}
			for(int j = 0;j<shortestPath.size();j++) {
				Node node = shortestPath.get(j).getDestinationNode();
				if("1".equals(node.getAttribute("DataCenter"))) {
					DCNodeOnPath.add(node);
				}
			}
			for(Node node:DCNodeOnPath) {
				if(!VNFOnDC.containsKey(node)) {
					List<Integer> reuse = new ArrayList<Integer>();
					for(String vnfType:VNFSeq) {
						reuse.add(Integer.valueOf(node.getAttribute(vnfType)));
					}
					VNFOnDC.put(node, Collections.max(reuse));
				}
			}
		}
		if(VNFOnDC.isEmpty()) {
			sign = false;
			nodeMappingReturn.setSign(sign);
			return nodeMappingReturn;
		}
		//取出具有最小属性的节点，将请求中的所有VNF都放到这个节点上
		int min = Collections.min(VNFOnDC.values());
		Node selectedDC = null ;
		for(Map.Entry<Node, Integer> it:VNFOnDC.entrySet()) {
			if(it.getValue()==min) {
				selectedDC = it.getKey();
				break;
			}
		}
		System.out.println("选中的数据中心"+subNodeList.indexOf(selectedDC));
		StringBuilder str = new StringBuilder();
		str.append(selectedDC.getAttribute("VNF"));
		for(String vnfType:VNFSeq) {
			int before = Integer.valueOf(selectedDC.getAttribute(vnfType)).intValue();
			if(before==0) {
				str.append(vnfType);
			}
			before++;
			selectedDC.setAttribute(vnfType, String.valueOf(before));
		}
		selectedDC.setAttribute("VNF", str.toString());
		for(int i=1;i<numberOfRequestNodes-1;i++) {
			nodePair.put(request.getNode(i), selectedDC);
			request.getNode(i).setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(selectedDC)));
		}
		for(Link link:requestLinkList) {
			int origin = subNodeList.indexOf(nodePair.get(link.getOriginNode()));
			int destination = subNodeList.indexOf(nodePair.get(link.getDestinationNode()));
			//System.out.println("origin node "+origin+" des node "+destination+" "+link.getCapacity());
			if(origin!=destination) {
				subNetPlan.addDemand(nodePair.get(link.getOriginNode()), nodePair.get(link.getDestinationNode()), link.getCapacity(), null, subNetPlan.getNetworkLayerDefault());
			}
		}
		nodeMappingReturn.setSign(sign);
		return nodeMappingReturn;
	}
	
	public static LinkMappingReturn linkMapping(NetPlan subNetPlan,NetPlan request) {
		List<Node> subNodes = subNetPlan.getNodes();
		List<Link> requestLinks = request.getLinks(request.getNetworkLayerDefault());
		LinkMappingReturn linkMappingReturn = new LinkMappingReturn();
		boolean  sign = true;
		System.out.println("demand "+subNetPlan.getNumberOfDemands(subNetPlan.getNetworkLayerDefault()));
		List<Demand> demandList = subNetPlan.getDemands(subNetPlan.getNetworkLayerDefault());
		Tool_Util tool = new Tool_Util();
		for(Demand demand: demandList) {
			double capacity = demand.getOfferedTraffic();
			System.out.println(capacity);
			Node startNode = demand.getIngressNode();
			Node endNode = demand.getEgressNode();
			Map<Link,Double> linkCostMap = new HashMap<Link,Double>();
			for(Link link:subNetPlan.getLinks()) {
				linkCostMap.put(link, link.getLengthInKm());
			}
			List<List<Link>> kShortestPathList = GraphUtils.getKLooplessShortestPaths(subNetPlan.getNodes(), subNetPlan.getLinks(), startNode, endNode, linkCostMap, numberOfKLinkmapping, Double.MAX_VALUE, Integer.MAX_VALUE , Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);
			List<List<Link>> candidatePathList = new ArrayList<List<Link>>();
			for(int i=0;i<numberOfKLinkmapping;i++) {
				List<Link> temppath = kShortestPathList.get(i);
				Double pathlength = 0.0;
				for(Link link:temppath) {
					pathlength=pathlength+link.getLengthInKm();
				}
				if(pathlength<=BPSKmaxlength) {
					candidatePathList.add(temppath);
				}
			}
			if(candidatePathList.isEmpty()) {
				removeAllLayerDemand(subNetPlan);
				sign = false;
				linkMappingReturn.setSign(sign);
				return linkMappingReturn;
			}
			List<Integer> mfsiList = new ArrayList<Integer>();
			List<Link> selectedPath = new ArrayList<Link>();
			for(int i=0;i<candidatePathList.size();i++) {
				List<Link> candidatePath = candidatePathList.get(i);
				double pathLength = 0.0;
				for(Link link :candidatePath) {
					pathLength+=link.getLengthInKm();
				}
				double modLevel = 0.0;
				int key = (int)(Math.floor(pathLength/QAM_16maxlength));
				switch(key) {
					case 1: modLevel = 4.0; break;
					case 2: modLevel = 3.0; break;
					case 3: modLevel = 2.0; break;
					case 4: modLevel = 2.0; break;
					default : modLevel = 1.0; break;
				}
				int numberofslotneeded = (int)Math.ceil(capacity/(12.5*modLevel));
				int[] pathStatus = new int[numberofallslot];
				for(Link link:candidatePath) {
					String linkStatus = link.getAttribute("linkstatus");
					int[] s1 = tool.stringToIntArray(linkStatus);
					for(int m =0;m<numberofallslot;m++) {
						if(pathStatus[m]==0&&s1[m]==0) {
							pathStatus[m]=0;
						}
						else {
							pathStatus[m]=1;
						}	
					}
				}
				int startindex = 0;
				int endindex = 0;
				int flag=0;
				int count = 0;
				for(int m=0;m<numberofallslot;m++) {
					count++;
					if(pathStatus[m]==0) {
						flag++;
					}
					else {
						flag=0;
					}
					if(flag==numberofslotneeded) {
						endindex = m;
						startindex = endindex-numberofslotneeded+1;
						break;
					}
				}
				if(count==numberofallslot&&endindex==0) {
					mfsiList.add(numberofallslot+1);
					continue;
				}
				for(int m =startindex;m<=endindex;m++) {
					pathStatus[m]=1;
				}
				int mfsi=0;
				for(int m=0;m<numberofallslot;m++) {
					if(pathStatus[m]==1) {
						mfsi=m+1;
					}
				}
				mfsiList.add(mfsi);
			}
			int kmin = Collections.min(mfsiList);
			if(kmin==numberofallslot+1) {
				removeAllLayerDemand(subNetPlan);
				sign = false;
				linkMappingReturn.setSign(sign);
				return linkMappingReturn;
			}
			int kindex = mfsiList.indexOf(kmin);
			selectedPath = candidatePathList.get(kindex);
			//铺设前整体的链路状态
			int [] pathStatusBefore = new int[numberofallslot];
			double pathLength = 0.0;
			for(Link link:selectedPath) {
				pathLength+=link.getLengthInKm();
			}
			String startNodeIndex = String.valueOf(subNodes.indexOf(startNode));
			String endNodeIndex = String.valueOf(subNodes.indexOf(endNode));
			for(Link link:requestLinks) {
				if(link.getOriginNode().getAttribute("MappedNode").equals(startNodeIndex)&&link.getDestinationNode().getAttribute("MappedNode").equals(endNodeIndex)) {
					link.setAttribute("pathlength", String.valueOf(pathLength));
					break;
				}
			}
			double modLevel = 0.0;
			int key = (int)(Math.floor(pathLength/QAM_16maxlength));
			switch(key) {
				case 1: modLevel = 4.0; break;
				case 2: modLevel = 3.0; break;
				case 3: modLevel = 2.0; break;
				case 4: modLevel = 2.0; break;
				default : modLevel = 1.0; break;
			}
			int numberofslotneeded = (int)Math.ceil(capacity/(12.5*modLevel));
			//System.out.println("numberofslotneeded "+numberofslotneeded);
			for(Link link:selectedPath) {
				String s = link.getAttribute("linkstatus");
				int[] s1 = tool.stringToIntArray(s);
				for(int m =0;m<numberofallslot;m++) {
					if(pathStatusBefore[m]==0&&s1[m]==0) {
						pathStatusBefore[m]=0;
					}
					else {
						pathStatusBefore[m]=1;
					}	
				}
			}
			int startindex = 0;
			int endindex = 0;
			int flag=0;
			for(int m=0;m<numberofallslot;m++) {
				if(pathStatusBefore[m]==0) {
					flag++;
				}
				else {
					flag=0;
				}
				if(flag==numberofslotneeded) {
					endindex = m;
					startindex = endindex-numberofslotneeded+1;
					break;
				}
			}
			for(Link link:selectedPath) {
				String s = link.getAttribute("linkstatus");
				int[] s1 = tool.stringToIntArray(s);
				for(int i =startindex;i<=endindex;i++) {
					s1[i]=1;
				}
				s = tool.intArrayToString(s1);
				link.setAttribute("linkstatus", s);
				//System.out.println("link "+subNodes.indexOf(link.getOriginNode())+"->"+subNodes.indexOf(link.getDestinationNode())+": "+link.getAttribute("linkstatus"));
			}
		}
		//铺设完链路之后，要删掉demand!!!!!!
		removeAllLayerDemand(subNetPlan);
		linkMappingReturn.setSign(sign);
		return linkMappingReturn;
	}
	
	public static int numberofDeployedVNF(NetPlan SubNetPlan) {
		int numberofdeployedvnf=0;
		List<Node> subnodelist = SubNetPlan.getNodes();
		for(Node node:subnodelist) {
			if(node.getAttribute("DataCenter").equals("1")) {
				int num=node.getAttribute("VNF").length()-1;
				numberofdeployedvnf=numberofdeployedvnf+num;
			}
		}	
		return numberofdeployedvnf;
	}
	
	public static int MFSI(NetPlan SubNetPlan) {
		int mfsiindex=0;
		Tool_Util tool = new Tool_Util();
		List<Link> subnetplanlinklist = SubNetPlan.getLinks(SubNetPlan.getNetworkLayerDefault());
		List<Integer> maxindexlist = new ArrayList<Integer>();
		for(Link link:subnetplanlinklist) {
			String s = link.getAttribute("linkstatus");
			int[] s1 = tool.stringToIntArray(s);
			int max = 0;
			for(int i =0;i<numberofallslot;i++) {
				if(s1[i]==1) {
					max=i;
				}
			}
			maxindexlist.add(max);
		}
		mfsiindex = Collections.max(maxindexlist);
		return mfsiindex+1;	
	}
	
	/**
	 * 对存放整数类型的集合求平均值
	 * @param list 存放整数类型对象的集合
	 * @return 平均值
	 */
	public static double getAvgvalue(List<Integer> list) {
		double avgvalue = 0.0;
		double sum = 0.0;
		int num = list.size();
		for(int i : list) {
			sum = (double)i+sum;	
		}
		avgvalue = sum/(num*1.0);
		return avgvalue;
	}
	
	/**
	 * 对存放Double类型对象的集合求平均值
	 * @param list 存放Double类型对象的集合
	 * @return 平均值
	 */
	public static double getDoubleAvgvalue(List<Double> list) {
		double avgvalue = 0.0;
		double sum = 0.0;
		int num = list.size();
		for(double i : list) {
			sum = (double)i+sum;	
		}
		avgvalue = sum/(num*1.0);
		return avgvalue;
	}
	
	
/**
 * 
 * @param index 要移动到末尾的元素序号
 * @param nodeList 要进行操作的集合
 */
	public static void moveToEnd(int index,List<Node>nodeList) {
		for(int i=index;i<nodeList.size()-1;i++) {
			Collections.swap(nodeList, i, i+1);
		}
	}
}
